BUFFSIZE = 900 * 1024

import time

def mtf(string):
    output=[]
    order = range(255)
    for c in string:
        i= order.index(ord(c))
        output.append(i)
        order.pop(i)
        order.insert(0,ord(c))
    return output

def inverse_mtf(input):
    output=[]
    order = range(255)
    for c in input:
        output.append(chr(order[c]))
        order.pop(c)
        order.insert(0,ord(output[-1]))
    return output

def mtf_improved(string):    
    output=[]
    
    order = get_lista()
        
    for c in string:
        i= order.index(ord(c))
        output.append(i)
        order.pop(i)
        order.insert(0,ord(c))
    return output

def inverse_mtf_improved(input,lista=[]):
    output=[]
    order = lista
    if( len(lista) == 0 ):
        order = get_lista()
    for c in input:
        output.append(chr(order[c]))
        order.pop(c)
        order.insert(0,ord(output[-1]))
    return output

def get_promedio(lista):
        suma = 0
        cantidad = 0
        for num in lista:
                suma += num
                cantidad += 1
        return (suma*1.00)/cantidad
		
def run_analysis_improved(filename):
	input_file = open(filename,'r')
	
	cont = 0
	
	buff = input_file.read(BUFFSIZE)
	texto_previamente_leido = ""
	texto_concatenado = buff
	
	while( len(buff) > 0 ):
		cont += 256
		
		start_time =  time.time() 
		mtf_output = mtf_improved(texto_concatenado)
		
		promedio = get_promedio(mtf_output)
		
		end_time = time.time() 
		
		if( (cont == 1) or (cont % 256 == 0) ):
			print "Promedio para %d Kb (%d Bytes) leidos: %f (time: %f segs)" % (int((len(texto_concatenado)/1024)),len(texto_concatenado),promedio,end_time-start_time)
		
		#print "Cont: "+str(cont)+"\n"
		
		if (cont >= 1024*30):
			break
		
		# Se acumulan el texto recien leido con lo leido previamente
		texto_previamente_leido = texto_previamente_leido + buff
		buff = input_file.read(BUFFSIZE)
		texto_concatenado = texto_previamente_leido + buff

	input_file.close()

def run_analysis_original(filename):
	input_file = open(filename,'r')
	
	cont = 0
	
	buff = input_file.read(BUFFSIZE)
	texto_previamente_leido = ""
	texto_concatenado = buff
	
	while( len(buff) > 0 ):
		cont += 256
		
		start_time =  time.time() 
		mtf_output = mtf(texto_concatenado)
		
		promedio = get_promedio(mtf_output)
		
		end_time = time.time() 
		
		if( (cont == 1) or (cont % 256 == 0) ):
			print "Promedio para %d Kb (%d Bytes) leidos: %f (time: %f segs)" % (int((len(texto_concatenado)/1024)),len(texto_concatenado),promedio,end_time-start_time)
		
		#print "Cont: "+str(cont)+"\n"
		
		if (cont >= 1024*30):
			break
		
		# Se acumulan el texto recien leido con lo leido previamente
		texto_previamente_leido = texto_previamente_leido + buff
		buff = input_file.read(BUFFSIZE)
		texto_concatenado = texto_previamente_leido + buff

	input_file.close()

def get_lista():
        lista = []
        lista.append(32)
        lista.append(101)
        lista.append(116)
        lista.append(97)
        lista.append(111)
        lista.append(110)
        lista.append(105)
        lista.append(104)
        lista.append(115)
        lista.append(114)
        lista.append(100)
        lista.append(108)
        lista.append(117)
        lista.append(13)
        lista.append(10)
        lista.append(109)
        lista.append(99)
        lista.append(119)
        lista.append(102)
        lista.append(103)
        lista.append(121)
        lista.append(44)
        lista.append(112)
        lista.append(98)
        lista.append(46)
        lista.append(118)
        lista.append(34)
        lista.append(107)
        lista.append(73)
        lista.append(45)
        lista.append(39)
        lista.append(84)
        lista.append(65)
        lista.append(59)
        lista.append(77)
        lista.append(72)
        lista.append(83)
        lista.append(67)
        lista.append(120)
        lista.append(87)
        lista.append(63)
        lista.append(66)
        lista.append(78)
        lista.append(68)
        lista.append(69)
        lista.append(33)
        lista.append(80)
        lista.append(113)
        lista.append(106)
        lista.append(76)
        lista.append(70)
        lista.append(71)
        lista.append(79)
        lista.append(82)
        lista.append(89)
        lista.append(122)
        lista.append(86)
        lista.append(49)
        lista.append(74)
        lista.append(48)
        lista.append(85)
        lista.append(95)
        lista.append(58)
        lista.append(75)
        lista.append(41)
        lista.append(40)
        lista.append(50)
        lista.append(53)
        lista.append(51)
        lista.append(52)
        lista.append(42)
        lista.append(91)
        lista.append(93)
        lista.append(81)
        lista.append(96)
        lista.append(56)
        lista.append(57)
        lista.append(54)
        lista.append(55)
        lista.append(88)
        lista.append(47)
        lista.append(90)
        lista.append(38)
        lista.append(124)
        lista.append(36)
        lista.append(64)
        lista.append(35)
        lista.append(37)
        lista.append(61)
        lista.append(125)
        lista.append(0)
        lista.append(1)
        lista.append(2)
        lista.append(3)
        lista.append(4)
        lista.append(5)
        lista.append(6)
        lista.append(7)
        lista.append(8)
        lista.append(9)
        lista.append(11)
        lista.append(12)
        lista.append(14)
        lista.append(15)
        lista.append(16)
        lista.append(17)
        lista.append(18)
        lista.append(19)
        lista.append(20)
        lista.append(21)
        lista.append(22)
        lista.append(23)
        lista.append(24)
        lista.append(25)
        lista.append(26)
        lista.append(27)
        lista.append(28)
        lista.append(29)
        lista.append(30)
        lista.append(31)
        lista.append(43)
        lista.append(60)
        lista.append(62)
        lista.append(92)
        lista.append(94)
        lista.append(123)
        lista.append(126)
        lista.append(127)
        lista.append(128)
        lista.append(129)
        lista.append(130)
        lista.append(131)
        lista.append(132)
        lista.append(133)
        lista.append(134)
        lista.append(135)
        lista.append(136)
        lista.append(137)
        lista.append(138)
        lista.append(139)
        lista.append(140)
        lista.append(141)
        lista.append(142)
        lista.append(143)
        lista.append(144)
        lista.append(145)
        lista.append(146)
        lista.append(147)
        lista.append(148)
        lista.append(149)
        lista.append(150)
        lista.append(151)
        lista.append(152)
        lista.append(153)
        lista.append(154)
        lista.append(155)
        lista.append(156)
        lista.append(157)
        lista.append(158)
        lista.append(159)
        lista.append(160)
        lista.append(161)
        lista.append(162)
        lista.append(163)
        lista.append(164)
        lista.append(165)
        lista.append(166)
        lista.append(167)
        lista.append(168)
        lista.append(169)
        lista.append(170)
        lista.append(171)
        lista.append(172)
        lista.append(173)
        lista.append(174)
        lista.append(175)
        lista.append(176)
        lista.append(177)
        lista.append(178)
        lista.append(179)
        lista.append(180)
        lista.append(181)
        lista.append(182)
        lista.append(183)
        lista.append(184)
        lista.append(185)
        lista.append(186)
        lista.append(187)
        lista.append(188)
        lista.append(189)
        lista.append(190)
        lista.append(191)
        lista.append(192)
        lista.append(193)
        lista.append(194)
        lista.append(195)
        lista.append(196)
        lista.append(197)
        lista.append(198)
        lista.append(199)
        lista.append(200)
        lista.append(201)
        lista.append(202)
        lista.append(203)
        lista.append(204)
        lista.append(205)
        lista.append(206)
        lista.append(207)
        lista.append(208)
        lista.append(209)
        lista.append(210)
        lista.append(211)
        lista.append(212)
        lista.append(213)
        lista.append(214)
        lista.append(215)
        lista.append(216)
        lista.append(217)
        lista.append(218)
        lista.append(219)
        lista.append(220)
        lista.append(221)
        lista.append(222)
        lista.append(223)
        lista.append(224)
        lista.append(225)
        lista.append(226)
        lista.append(227)
        lista.append(228)
        lista.append(229)
        lista.append(230)
        lista.append(231)
        lista.append(232)
        lista.append(233)
        lista.append(234)
        lista.append(235)
        lista.append(236)
        lista.append(237)
        lista.append(238)
        lista.append(239)
        lista.append(240)
        lista.append(241)
        lista.append(242)
        lista.append(243)
        lista.append(244)
        lista.append(245)
        lista.append(246)
        lista.append(247)
        lista.append(248)
        lista.append(249)
        lista.append(250)
        lista.append(251)
        lista.append(252)
        lista.append(253)
        lista.append(254)
        lista.append(255)
        return lista
